
import java.util.*;
public class Solution
{
    public int LIS (int[] a)
    {
        int n = a.length;
        int[] dp = new int[n + 1]; // dp[i] 表⽰⻓度为 i 的最⼩末尾
        int pos = 0;
        for(int x : a) {
            // 找 x 应该放在哪⾥
            if(pos == 0 || x > dp[pos]) {
                dp[++pos] = x;
            } else {
                // ⼆分查找插⼊位置
                int l = 1, r = pos;
                while(l < r) {
                    int mid = (l + r) / 2;
                    if(dp[mid] >= x)
                        r = mid;
                    else
                        l = mid + 1;
                }
                dp[l] = x;
            }
        }
        return pos;
    }
}

